package evaluation;

/**
 * 逆序对问题，小和问题的同样实现()
 */
public class ReverseOrder {
    public static void process(int[] arrs,int l,int r){
        if (l==r){
            return;
        }
        int mid = l + ((r-l) >> 1);
        process(arrs,l,mid);
        process(arrs,mid+1,r);
        merge(arrs,l,mid,r);
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        int help[] = new int[r-l+1];
        int i=0;
        int p1 = l;
        int p2 =mid + 1;
        //算出值
        while (p1 <= mid && p2<=r){
            if (arr[p1] > arr[p2]){
                System.out.println("{"+arr[p1]+","+arr[p2]+"}");
            }
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1<=mid){
            help[i++] = arr[p1++];
        }
        while (p2<=r){
            help[i++] = arr[p2++];
        }
        //排序
        for (int i2 = 0; i2 < help.length; i2++) {
            arr[l+i2] = help[i2];
        }
    }
    public static void main(String[] args) {
        int[] arrs = {1,3,4,2,5};
        process(arrs,0,arrs.length-1);
        for (int arr : arrs) {
            System.out.println(arr);
        }
    }
}
